package com.murphy.algorithm.likou;

import com.alibaba.fastjson.JSON;

import java.util.*;

/**
 * 滑动窗口内最大的值
 * @author dongsufeng
 * @version 4.0
 * @date 2023/2/22 15:03
 */
public class MaxSlidingWindow {

    public List<Integer> max1(int[] nums, int windowSize){
        //存下表
        Deque<Integer> deque = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            //不等于空&& 当前数大于队列最后一个移除，结果就是前面都是比当前数大的
            while (!deque.isEmpty() && nums[i]>=nums[deque.getLast()]) {
                deque.pollLast();
            }
            //窗口移出去的数据移除
            while (!deque.isEmpty() && i-(windowSize-1)>deque.getFirst()){
                deque.pollFirst();
            }
            deque.offerLast(i);
            if (i+1>=windowSize){
                System.out.println(nums[deque.peekFirst()]);
                result.add(nums[deque.peekFirst()]);
            }
        }
        return result;
    }

    public List<Integer> max(int[] nums, int windowSize){
        List<Integer> result = new ArrayList<>();
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            if (i < windowSize-1){
                deque.offerLast(i);
                continue;
            }
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]){
                deque.pollLast();
            }
            deque.offerLast(i);
            if (!deque.isEmpty() && deque.getFirst() < i+1 - windowSize){
                deque.pollFirst();
            }
            result.add(nums[deque.peekFirst()]);
        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {1,3,4,5,62,3,9,6,7,82,8,3,32,3,4};
        MaxSlidingWindow window = new MaxSlidingWindow();
        List<Integer> list=window.max(nums,3);
        System.out.println(JSON.toJSON(list));
    }
}
